import java.util.HashMap;

public class Solution {
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    public static boolean isSame(TreeNode root1,TreeNode root2){
        if(root2==null){
            return true;
        }else if(root1==null){
            return false;
        }
        
        if(root1.val == root2.val)
            return isSame(root1.left,root2.left) && isSame(root1.right,root2.right);
        else
            return false;

    }
    public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null)
            return false;
        else if(root1!=null){
            if(isSame(root1,root2))
                return true;
            else
                return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
        }else{
            return false;
        }


    }
    public static void main(String args[]){
//{8,#,8,#,9,#,2,#,5},{8,#,9,3,2}

        TreeNode root1 = new TreeNode(8);
        root1.left = null;
        root1.right = new TreeNode(8);
        root1.left.left = new TreeNode(4);
        root1.left.right = new TreeNode(5);
        root1.right.left = null;
        root1.right.right = null;

        root1.left.left.left = null;
        root1.left.left.right = null;

        TreeNode root2 = new TreeNode(2);
        root2.left = new TreeNode(4);
        root2.right = new TreeNode(5);
        boolean result = HasSubtree(root1,root2);
        System.out.println(result);
    }
}